{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Distribute Repeating Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canDistribute"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分配重复整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为&nbsp;<code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;，这个数组中至多有&nbsp;<code>50</code>&nbsp;个不同的值。同时你有 <code>m</code>&nbsp;个顾客的订单 <code>quantity</code>&nbsp;，其中，整数&nbsp;<code>quantity[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;位顾客订单的数目。请你判断是否能将 <code>nums</code>&nbsp;中的整数分配给这些顾客，且满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>第&nbsp;<code>i</code>&nbsp;位顾客 <strong>恰好&nbsp;</strong>有&nbsp;<code>quantity[i]</code>&nbsp;个整数。</li>\n",
    "\t<li>第&nbsp;<code>i</code>&nbsp;位顾客拿到的整数都是 <strong>相同的</strong>&nbsp;。</li>\n",
    "\t<li>每位顾客都满足上述两个要求。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果你可以分配 <code>nums</code>&nbsp;中的整数满足上面的要求，那么请返回&nbsp;<code>true</code>&nbsp;，否则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3,4], quantity = [2]\n",
    "<b>输出：</b>false\n",
    "<strong>解释：</strong>第 0 位顾客没办法得到两个相同的整数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3,3], quantity = [2]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,1,2,2], quantity = [2,2]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>m == quantity.length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 10</code></li>\n",
    "\t<li><code>1 &lt;= quantity[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;中至多有&nbsp;<code>50</code>&nbsp;个不同的数字。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [distribute-repeating-integers](https://leetcode.cn/problems/distribute-repeating-integers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [distribute-repeating-integers](https://leetcode.cn/problems/distribute-repeating-integers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n[2]', '[1,2,3,3]\\n[2]', '[1,1,2,2]\\n[2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        vals = sorted(list(cnt.values()), reverse=True)\n",
    "        m = len(quantity)\n",
    "        quantity.sort(reverse=True)\n",
    "\n",
    "        #当前可以匹配的集合为tup，已经匹配了j个人\n",
    "        @cache\n",
    "        def dfs(tup, j):\n",
    "            if j == m:\n",
    "                return True\n",
    "            for i in range(len(tup)):\n",
    "                if tup[i] >= quantity[j]:\n",
    "                    arr = list(tup)\n",
    "                    arr[i] -= quantity[j]\n",
    "                    arr.sort(reverse=True)\n",
    "                    if dfs(tuple(arr), j + 1):\n",
    "                        return True\n",
    "                else:\n",
    "                    break\n",
    "            return False\n",
    "\n",
    "        res = dfs(tuple(vals), 0)\n",
    "        del dfs\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        vals = sorted([x for x in cnt.values()], reverse=True)\n",
    "        m = len(quantity)\n",
    "        quantity.sort(reverse=True)\n",
    "\n",
    "        #当前可以匹配的集合为tup，已经匹配了j个人\n",
    "        @cache\n",
    "        def dfs(tup, j):\n",
    "            if j == m:\n",
    "                return True\n",
    "            arr = list(tup)\n",
    "            for i in range(len(arr)):\n",
    "                if arr[i] >= quantity[j]:\n",
    "                    new_arr = arr[:i] + [arr[i] - quantity[j]] + arr[i + 1:]\n",
    "                    new_arr.sort(reverse=True)\n",
    "                    if dfs(tuple(new_arr), j + 1):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        res = dfs(tuple(vals), 0)\n",
    "        del dfs\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        nums = list(cnt.values())\n",
    "        quantity.sort(reverse=True)\n",
    "        @cache\n",
    "        def back(cur,use):\n",
    "            if cur == len(quantity):return True\n",
    "            if use[-1] < quantity[cur]:return False\n",
    "            lin = list(use)\n",
    "            for i in range(len(lin)-1,-1,-1):\n",
    "                if lin[i] >= quantity[cur]:\n",
    "                    lin[i] -= quantity[cur]\n",
    "                    if back(cur+1,tuple(sorted(lin))):return True\n",
    "                    lin[i] += quantity[cur]\n",
    "            return False\n",
    "        res = back(0,tuple(sorted(nums)))\n",
    "        del back\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        nums = list(cnt.values())\n",
    "        quantity.sort(reverse=True)\n",
    "        # @cache\n",
    "        def back(cur,use):\n",
    "            if cur == len(quantity):return True\n",
    "            if use[-1] < quantity[cur]:return False\n",
    "            lin = list(use)\n",
    "            for i in range(len(lin)-1,-1,-1):\n",
    "                if lin[i] >= quantity[cur]:\n",
    "                    lin[i] -= quantity[cur]\n",
    "                    if back(cur+1,tuple(sorted(lin))):return True\n",
    "                    lin[i] += quantity[cur]\n",
    "            return False\n",
    "        res = back(0,tuple(sorted(nums)))\n",
    "        del back\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        \n",
    "        # Count the occurrences of numbers\n",
    "        count = list(Counter(nums).values())\n",
    "        \n",
    "        # Sort the quantity list to prioritize larger orders\n",
    "        quantity.sort(reverse=True)\n",
    "\n",
    "        # Helper function for backtracking\n",
    "        def backtrack(idx, counts):\n",
    "            # If we have satisfied all orders, return True\n",
    "            if idx == len(quantity):\n",
    "                return True\n",
    "\n",
    "            # Check each count to see if we can fulfill the order\n",
    "            for i, c in enumerate(counts):\n",
    "                if c >= quantity[idx]:\n",
    "                    # Try to use this count to satisfy the order\n",
    "                    counts[i] -= quantity[idx]\n",
    "                    \n",
    "                    # If we can fulfill the subsequent orders, return True\n",
    "                    if backtrack(idx + 1, counts):\n",
    "                        return True\n",
    "                    \n",
    "                    # Otherwise, backtrack\n",
    "                    counts[i] += quantity[idx]\n",
    "\n",
    "            # If we can't satisfy the order, return False\n",
    "            return False\n",
    "        \n",
    "        return backtrack(0, count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        nums = list(cnt.values())\n",
    "        quantity.sort(reverse=True)\n",
    "        @cache\n",
    "        def back(cur,use):\n",
    "            if cur == len(quantity):return True\n",
    "            if use[-1] < quantity[cur]:return False\n",
    "            lin = list(use)\n",
    "            for i in range(len(lin)-1,-1,-1):\n",
    "                if lin[i] >= quantity[cur]:\n",
    "                    lin[i] -= quantity[cur]\n",
    "                    if back(cur+1,tuple(sorted(lin))):return True\n",
    "                    lin[i] += quantity[cur]\n",
    "            return False\n",
    "        res = back(0,tuple(sorted(nums)))\n",
    "        del back\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        nums = list(cnt.values())\n",
    "        quantity.sort(reverse=True)\n",
    "        @cache\n",
    "        def back(cur,use):\n",
    "            if cur == len(quantity):return True\n",
    "            if use[-1] < quantity[cur]:return False\n",
    "            lin = list(use)\n",
    "            for i in range(len(lin)-1,-1,-1):\n",
    "                if lin[i] >= quantity[cur]:\n",
    "                    lin[i] -= quantity[cur]\n",
    "                    if back(cur+1,tuple(sorted(lin))):return True\n",
    "                    lin[i] += quantity[cur]\n",
    "            return False\n",
    "        res = back(0,tuple(sorted(nums)))\n",
    "        # del back\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 2023-09-21 22:07:39\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        v = list(cnt.values())\n",
    "\n",
    "        m = len(quantity)\n",
    "        N = 1 << m\n",
    "        dp = [False] * N\n",
    "        dp[0] = True\n",
    "\n",
    "        @cache\n",
    "        def f(mask: int):\n",
    "            return sum(x for i, x in enumerate(quantity) if mask >> i & 1)\n",
    "\n",
    "        for x in v:\n",
    "            dp_next = dp.copy()\n",
    "            for mask in range(N):\n",
    "                sub = mask\n",
    "                while sub and not dp_next[mask]:\n",
    "                    # print(mask, sub, mask ^ sub, f(mask ^ sub))\n",
    "                    dp_next[mask] = dp[mask ^ sub] and (f(sub) <= x)\n",
    "                    sub = mask & (sub - 1)\n",
    "            dp = dp_next\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        nums = list(cnt.values())\n",
    "        quantity.sort(reverse=True)\n",
    "        @cache\n",
    "        def back(cur,use):\n",
    "            if cur == len(quantity):return True\n",
    "            if use[-1] < quantity[cur]:return False\n",
    "            lin = list(use)\n",
    "            for i in range(len(lin)-1,-1,-1):\n",
    "                if lin[i] >= quantity[cur]:\n",
    "                    lin[i] -= quantity[cur]\n",
    "                    if back(cur+1,tuple(sorted(lin))):return True\n",
    "                    lin[i] += quantity[cur]\n",
    "            return False\n",
    "        res = back(0,tuple(sorted(nums)))\n",
    "        del back\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        m = len(quantity)\n",
    "        arr = sorted(Counter(nums).values(), reverse=True)\n",
    "        quantity.sort(reverse=True)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == m:\n",
    "                return True\n",
    "            pre = -1\n",
    "            for j, x in enumerate(arr):\n",
    "                if x < quantity[i] or x == pre:\n",
    "                    continue\n",
    "                pre = x\n",
    "                arr[j] -= quantity[i]\n",
    "                if dfs(i+1):\n",
    "                    return True\n",
    "                arr[j] += quantity[i]\n",
    "            return False\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt, m = Counter(nums), len(quantity)\n",
    "        quantity.sort(reverse=True)\n",
    "        L = sorted(cnt.values())[-m: ]\n",
    "        if sum(L) < sum(quantity) or quantity[0] > max(L): return False\n",
    "        ans = False\n",
    "        L.sort()\n",
    "        \n",
    "        def f(i):\n",
    "            nonlocal ans\n",
    "            if ans: return \n",
    "            if i == m:\n",
    "                ans = True \n",
    "                return \n",
    "            \n",
    "            for j, val in enumerate(L):\n",
    "                if val >= quantity[i]:\n",
    "                    L[j] -= quantity[i]\n",
    "                    f(i + 1)\n",
    "                    L[j] += quantity[i]\n",
    "        \n",
    "        f(0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        nums = list(Counter(nums).values())\n",
    "        quantity.sort(reverse=True)\n",
    "        m, n = len(quantity), len(nums)\n",
    "\n",
    "        def dfs(idx):\n",
    "            if idx == m:\n",
    "                return True\n",
    "\n",
    "            q = quantity[idx]\n",
    "            for i in range(n):\n",
    "                if nums[i] >= q:\n",
    "                    nums[i] -= q\n",
    "                    if dfs(idx + 1):\n",
    "                        return True\n",
    "                    nums[i] += q\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i ==n or ans :\n",
    "                ans = True\n",
    "                return True\n",
    "            for j in range(m):\n",
    "                if cnt[j] >= quantity[i]:\n",
    "                    cnt[j] -= quantity[i]\n",
    "                    dfs(i + 1)\n",
    "                    cnt[j] += quantity[i]\n",
    "            return \n",
    "\n",
    "\n",
    "        cnt = sorted(list(Counter(nums).values()), reverse=True)\n",
    "        quantity.sort(reverse = True)\n",
    "\n",
    "        m = len(cnt)\n",
    "        n = len(quantity)\n",
    "        ans = False\n",
    "        dfs(0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        nums = list(cnt.values())\n",
    "        quantity.sort(reverse=True)\n",
    "        @cache\n",
    "        def back(cur,use):\n",
    "            if cur == len(quantity):return True\n",
    "            if use[-1] < quantity[cur]:return False\n",
    "            lin = list(use)\n",
    "            for i in range(len(lin)-1,-1,-1):\n",
    "                if lin[i] >= quantity[cur]:\n",
    "                    lin[i] -= quantity[cur]\n",
    "                    if back(cur+1,tuple(sorted(lin))):return True\n",
    "                    lin[i] += quantity[cur]\n",
    "            return False\n",
    "        res = back(0,tuple(sorted(nums)))\n",
    "        # del back\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self,nums, quantity):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type quantity: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        count = [0] * 1001\n",
    "        temp = 0\n",
    "        for val in nums:\n",
    "            if count[val] == 0:\n",
    "                temp += 1\n",
    "            count[val] += 1\n",
    "        count.sort(reverse=True)\n",
    "        count = count[:temp]\n",
    "        quantity.sort(reverse=True)\n",
    "\n",
    "        @cache\n",
    "        def getResult(index, count):\n",
    "            if index == len(quantity):\n",
    "                return True\n",
    "\n",
    "            for i in range(len(count)):\n",
    "                newCount = list(count)\n",
    "                if newCount[i] >= quantity[index]:\n",
    "                    newCount[i] -= quantity[index]\n",
    "                    newCount.sort(reverse=True)\n",
    "                    if getResult(index + 1, tuple(newCount)):\n",
    "                        return True\n",
    "                else:\n",
    "                    break\n",
    "            return False\n",
    "\n",
    "        return getResult(0, tuple(count))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        nums = list(cnt.values())\n",
    "        quantity.sort(reverse=True)\n",
    "        @cache\n",
    "        def back(cur,use):\n",
    "            if cur == len(quantity):return True\n",
    "            if use[-1] < quantity[cur]:return False\n",
    "            lin = list(use)\n",
    "            for i in range(len(lin)-1,-1,-1):\n",
    "                if lin[i] >= quantity[cur]:\n",
    "                    lin[i] -= quantity[cur]\n",
    "                    if back(cur+1,tuple(sorted(lin))):return True\n",
    "                    lin[i] += quantity[cur]\n",
    "            return False\n",
    "        res = back(0,tuple(sorted(nums)))\n",
    "        del back\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == n or ans:\n",
    "                ans = True\n",
    "                return\n",
    "            for j in range(m):\n",
    "                if cnt[j] >= quantity[i]:\n",
    "                    cnt[j] -= quantity[i]\n",
    "                    dfs(i + 1)\n",
    "                    cnt[j] += quantity[i]\n",
    "            return\n",
    "\n",
    "        cnt = sorted(list(Counter(nums).values()), reverse=True)\n",
    "        quantity.sort(reverse=True) # 排序是不超时关键\n",
    "        m = len(cnt)\n",
    "        n = len(quantity)\n",
    "        ans = False\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: list[int], quantity: list[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        quantity.sort()\n",
    "        def dfs():\n",
    "            if not quantity:\n",
    "                return True\n",
    "            curr = quantity.pop()\n",
    "            keys = list(filter(lambda x: cnt[x] >= curr, cnt))\n",
    "            for key in keys:\n",
    "                cnt[key] -= curr\n",
    "                if dfs():\n",
    "                    return True\n",
    "                cnt[key] += curr\n",
    "            quantity.append(curr)\n",
    "            return False\n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        n,m = len(nums),len(quantity)\n",
    "        if sum(quantity) > n:return False\n",
    "        C = Counter(nums)\n",
    "        quantity.sort(key = lambda x:-x)\n",
    "        def dfs(pos):\n",
    "            if pos == m:return True\n",
    "            for idx,v in C.items():\n",
    "                if v >= quantity[pos]:\n",
    "                    C[idx] -= quantity[pos]\n",
    "                    if dfs(pos+1):return True\n",
    "                    C[idx] += quantity[pos]\n",
    "            return False\n",
    "\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt, m = Counter(nums), len(quantity)\n",
    "        quantity.sort(reverse=True)\n",
    "        L = sorted(cnt.values())[-m: ]\n",
    "        if sum(L) < sum(quantity) or quantity[0] > max(L): return False\n",
    "        ans = False\n",
    "        \n",
    "        \n",
    "        def f(i, tup):\n",
    "            nonlocal ans\n",
    "            if ans: return \n",
    "            if i == m:\n",
    "                ans = True \n",
    "                return \n",
    "            tup = list(tup)\n",
    "            for j, val in enumerate(tup):\n",
    "                if val >= quantity[i]:\n",
    "                    tup[j] -= quantity[i]\n",
    "                    f(i + 1, tuple(tup))\n",
    "                    tup[j] += quantity[i]\n",
    "        \n",
    "        f(0, tuple(L))\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param quantity:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = {}\n",
    "        for i in nums:\n",
    "            if i not in m1:\n",
    "                m1[i] = 1\n",
    "            else:\n",
    "                m1[i] += 1\n",
    "        ll = list(m1.values())\n",
    "        ll.sort(reverse=True)\n",
    "        self.ll = ll\n",
    "        self.len1 = len(quantity)\n",
    "        self.q = quantity\n",
    "\n",
    "        res = self.getAns(0, self.ll)\n",
    "        return res\n",
    "\n",
    "    def getAns(self, idx, ll):\n",
    "        if idx == self.len1:\n",
    "            return True\n",
    "        cur = self.q[idx]\n",
    "        rest = self.q[idx:]\n",
    "        if max(rest) > max(ll):\n",
    "            return False\n",
    "        for k,v in enumerate(ll):\n",
    "            if v >= cur:\n",
    "                ll[k] -= cur\n",
    "                ans = self.getAns(idx+1, ll)\n",
    "                if ans:\n",
    "                    return ans\n",
    "                ll[k] += cur\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        tmp = Counter(nums)\n",
    "        cnt = []\n",
    "        for k, v in tmp.items():\n",
    "            cnt.append(v)\n",
    "        \n",
    "        n, m = len(cnt), len(quantity)\n",
    "        mask = 1<<m\n",
    "        ssum = [0] * mask\n",
    "        for i in range(1, mask):\n",
    "            for j in range(m):\n",
    "                if i &(1<<j) != 0:\n",
    "                    ssum[i] = ssum[i-(1<<j)] + quantity[j]\n",
    "                    break\n",
    "        print(ssum)\n",
    "        f = [[False] * (mask) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            f[i][0] = True\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(mask):\n",
    "                if i>0 and f[i-1][j]:\n",
    "                    f[i][j] = True\n",
    "                    continue\n",
    "                s = j\n",
    "                while s:\n",
    "                    prev = j-s\n",
    "                    if i == 0:\n",
    "                        last = (prev ==0)\n",
    "                    else:\n",
    "                        last = f[i-1][prev]\n",
    "                    \n",
    "                    need = ssum[s]<=cnt[i]\n",
    "                    if last and need:\n",
    "                        f[i][j] = True\n",
    "                        break\n",
    "                    s = (s-1)&j\n",
    " \n",
    "        return f[-1][-1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnt = list(Counter(nums).values())\n",
    "        n, m = len(cnt), len(quantity)\n",
    "\n",
    "        summ = [0] * (1 << m)\n",
    "        for mask in range(1, 1 << m):\n",
    "            for i in range(m):\n",
    "                if mask & (1 << i):\n",
    "                    left = mask - (1 << i)\n",
    "                    summ[mask] = summ[left] + quantity[i]\n",
    "                    break\n",
    "\n",
    "        # dp[i][j]: freq 数组中的前 i 个元素，能够满足顾客子集 j 的订单需求\n",
    "        dp = [[False] * (1 << m) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(1 << m):\n",
    "                if i > 0 and dp[i - 1][j]:\n",
    "                    dp[i][j] = True\n",
    "                    continue\n",
    "\n",
    "                s = j\n",
    "                while s > 0:\n",
    "                    prev = j - s\n",
    "                    last = prev == 0 if i == 0 else dp[i - 1][prev]\n",
    "                    need = summ[s] <= cnt[i]\n",
    "                    if last and need:\n",
    "                        dp[i][j] = True\n",
    "                        break\n",
    "\n",
    "                    s = (s - 1) & j\n",
    "\n",
    "        return dp[n - 1][(1 << m) - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        n = len(quantity)\n",
    "        # 状态压缩的dp\n",
    "        data = list(Counter(nums).values())\n",
    "        al = (1 << n) - 1\n",
    "        sm = [0 for _ in range(al + 1)]\n",
    "        # 每个状态单独由一个数字处理需要多大\n",
    "        for i in range(1, 1 << n):\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1:\n",
    "                    sm[i] = sm[i - (1 << j)] + quantity[j]\n",
    "                    break\n",
    "        f = [[False for _ in range(1 << n)] for _ in range(len(data) + 1)]\n",
    "\n",
    "        for i in range(len(data)):\n",
    "            f[i][0] = True\n",
    "            for state in range(1, al + 1):\n",
    "                other = state\n",
    "                while True:\n",
    "                    if sm[other] <= data[i] and f[i][state-other]:\n",
    "                        f[i+1][state] = True\n",
    "                    other = (other - 1) & state\n",
    "                    if other == state:\n",
    "                        break\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "记忆化递归，枚举quantidy中的每一个数值应该放到哪个容器中\n",
    "找到一种合法方案即返回True\n",
    "'''\n",
    "\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        c = Counter(nums)\n",
    "        m = len(quantity)\n",
    "        containers = [val for val in c.values()]\n",
    "        containers.sort(reverse=True)\n",
    "        containers = containers[:m]\n",
    "\n",
    "        quantity.sort()\n",
    "\n",
    "        # con表示的容器容量元组能否容纳下quantitiy中前i项\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(con, i):\n",
    "            if i == -1:\n",
    "                return True\n",
    "\n",
    "            if quantity[i] > con[0]:\n",
    "                return False\n",
    "\n",
    "            for j in range(len(con)):\n",
    "                if con[j] >= quantity[i]:\n",
    "                    new_con = list(con)\n",
    "                    new_con[j] -= quantity[i]\n",
    "                    new_con.sort(reverse=True)\n",
    "\n",
    "                    if dp(tuple(new_con), i-1):\n",
    "                        return True\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            return False\n",
    "\n",
    "\n",
    "        return dp(tuple(containers), m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        n = len(quantity)\n",
    "        # 状态压缩的dp\n",
    "        data = list(Counter(nums).values())\n",
    "        al = (1 << n) - 1\n",
    "        sm = [0 for _ in range(al + 1)]\n",
    "        # 每个状态单独由一个数字处理需要多大的数字\n",
    "        for i in range(1, 1 << n):\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1:\n",
    "                    sm[i] = sm[i - (1 << j)] + quantity[j]\n",
    "                    break\n",
    "        f = [[False for _ in range(al + 1)] for _ in range(len(data))]\n",
    "        for i in range(len(data)):\n",
    "            f[i][0] = True\n",
    "        for i in range(len(data)):\n",
    "            for state in range(1, al + 1):\n",
    "                if i > 0 and f[i-1][state]:\n",
    "                    f[i][state] = True\n",
    "                    continue\n",
    "                cur = state\n",
    "                while cur != 0:\n",
    "                    left = state - cur\n",
    "                    last = left == 0 if i == 0 else f[i-1][left]\n",
    "                    if sm[cur] <= data[i] and last:\n",
    "                        f[i][state] = True\n",
    "                        break\n",
    "                    cur = (cur - 1) & state\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        x = sorted(Counter(nums).values(), reverse=True)\n",
    "        quantity.sort(reverse=True)\n",
    "        while x and x[-1] < quantity[-1]:\n",
    "            x.pop()\n",
    "        n, m = len(x), len(quantity)\n",
    "        s = [[] for _ in range(n)]\n",
    "        for j,v in enumerate(x):\n",
    "            selected = t = 0\n",
    "            def dfs(i):\n",
    "                nonlocal selected, t\n",
    "                if t > v: return\n",
    "                if i == m:\n",
    "                    for k in range(m):\n",
    "                        if selected & (1<<k) == 0 and t + quantity[k] <= v:\n",
    "                            return\n",
    "                    s[j].append(selected)\n",
    "                    return\n",
    "                dfs(i+1)\n",
    "                selected |= 1<<i\n",
    "                t += quantity[i]\n",
    "                dfs(i+1)\n",
    "                t -= quantity[i]\n",
    "                selected ^= 1<<i\n",
    "            dfs(0)\n",
    "\n",
    "        @cache\n",
    "        def dfs2(i, cur):\n",
    "            if cur == (1<<m) - 1:\n",
    "                return True\n",
    "            if i == n:\n",
    "                return False\n",
    "            for p in s[i]:\n",
    "                if p | cur == cur: continue\n",
    "                if dfs2(i+1, p | cur):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs2(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        x = sorted(Counter(nums).values(), reverse=True)\n",
    "        quantity.sort(reverse=True)\n",
    "        m = len(quantity)\n",
    "        x = x[:m]\n",
    "        s = [[] for _ in range(m)]\n",
    "        for j,v in enumerate(x):\n",
    "            def dfs(i, selected, total):\n",
    "                if total > v: return\n",
    "                if i == m:\n",
    "                    for k in range(m):\n",
    "                        if selected & (1<<k) == 0 and total + quantity[k] <= v:\n",
    "                            return\n",
    "                    s[j].append(selected)\n",
    "                    return\n",
    "                dfs(i+1, selected, total)\n",
    "                dfs(i+1, selected | (1<<i), total + quantity[i])\n",
    "            dfs(0, 0, 0)\n",
    "\n",
    "        @cache\n",
    "        def dfs2(i, cur):\n",
    "            if cur == (1<<m) - 1:\n",
    "                return True\n",
    "            if i == m:\n",
    "                return False\n",
    "            for p in s[i]:\n",
    "                if p | cur == cur: continue\n",
    "                if dfs2(i+1, p | cur):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs2(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(pos,k,v):\n",
    "  if 1<<pos > k:L[k].append(v);return\n",
    "  if not (1 & k >> pos):dfs(pos+1,k,v)\n",
    "  else:\n",
    "    dfs(pos+1,k,v)\n",
    "    dfs(pos+1,k,v+(1<<pos))\n",
    "  return\n",
    "L = [None] * 1024\n",
    "for i in range(1024):\n",
    "  L[i] = []\n",
    "  dfs(0,i,0)\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        n,m = len(nums),len(quantity)\n",
    "        if sum(quantity) > n:return False\n",
    "        C = Counter(nums);l = len(list(C.keys()))\n",
    "        D = [0] * l\n",
    "        mx = 2**m\n",
    "        pos = 0\n",
    "        for i in C.values():\n",
    "            D[pos] = i;pos += 1\n",
    "\n",
    "        F = [[False] * mx for i in range(l+1)]\n",
    "        F[0][0] = True\n",
    "        for i in range(l+1):F[i][0] = True\n",
    "        \n",
    "        G = [0]*mx\n",
    "        for k in range(mx):\n",
    "            pos = 0;x = 0\n",
    "            while k >= 1 << pos:\n",
    "                if k >> pos & 1:x += quantity[pos]\n",
    "                pos += 1\n",
    "            G[k] = x\n",
    "        def f(k,v):\n",
    "            return G[k] <= v\n",
    "        \n",
    "        for i in range(1,l+1):\n",
    "            v = D[i-1]\n",
    "            for comb in range(1,mx):\n",
    "                for sub in L[comb]:\n",
    "                    if F[i][comb]:break\n",
    "                    F[i][comb] = f(sub,v) and F[i-1][comb-sub]\n",
    "        return F[-1][-1]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(pos,k,v):\n",
    "    if 1<<pos > k:L[k].append(v);return\n",
    "    if not (1 & k >> pos):dfs(pos+1,k,v)\n",
    "    else:\n",
    "        dfs(pos+1,k,v)\n",
    "        dfs(pos+1,k,v+(1<<pos))\n",
    "    return\n",
    "L = [None] * 1024\n",
    "for i in range(1024):\n",
    "    L[i] = []\n",
    "    dfs(0,i,0)\n",
    "    L[i].reverse()\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        n,m = len(nums),len(quantity)\n",
    "        if sum(quantity) > n:return False\n",
    "        C = Counter(nums);l = len(list(C.keys()))\n",
    "        D = [0] * l\n",
    "        mx = 2**m\n",
    "        pos = 0\n",
    "        for i in C.values():\n",
    "            D[pos] = i;pos += 1\n",
    "        D.sort(reverse = True)\n",
    "        F = [[False] * mx for i in range(l+1)]\n",
    "        F[0][0] = True\n",
    "        for i in range(l+1):F[i][0] = True\n",
    "        \n",
    "        G = [0]*mx\n",
    "        for k in range(mx):\n",
    "            pos = 0;x = 0\n",
    "            while k >= 1 << pos:\n",
    "                if k >> pos & 1:x += quantity[pos]\n",
    "                pos += 1\n",
    "            G[k] = x\n",
    "        def f(k,v):\n",
    "            return G[k] <= v\n",
    "        \n",
    "        for i in range(1,l+1):\n",
    "            v = D[i-1]\n",
    "            for comb in range(1,mx):\n",
    "                for sub in L[comb]:\n",
    "                    if F[i][comb]:break\n",
    "                    F[i][comb] = f(sub,v) and F[i-1][comb-sub]\n",
    "        return F[-1][-1]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(pos,k,v):\n",
    "  if 1<<pos > k:L[k].append(v);return\n",
    "  if not (1 & k >> pos):dfs(pos+1,k,v)\n",
    "  else:\n",
    "    dfs(pos+1,k,v)\n",
    "    dfs(pos+1,k,v+(1<<pos))\n",
    "  return\n",
    "L = [None] * 1024\n",
    "for i in range(1024):\n",
    "  L[i] = []\n",
    "  dfs(0,i,0)\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        n,m = len(nums),len(quantity)\n",
    "        if sum(quantity) > n:return False\n",
    "        C = Counter(nums);l = len(list(C.keys()))\n",
    "        D = [0] * l\n",
    "        mx = 2**m\n",
    "        pos = 0\n",
    "        for i in C.values():\n",
    "            D[pos] = i;pos += 1\n",
    "\n",
    "        F = [[False] * mx for i in range(l+1)]\n",
    "        F[0][0] = True\n",
    "        for i in range(l+1):F[i][0] = True\n",
    "        G = {}\n",
    "        for i in range(1,l+1):\n",
    "            v = D[i-1]\n",
    "            for comb in range(1,mx):\n",
    "                for sub in L[comb]:\n",
    "                    if F[i][comb]:break\n",
    "                    if sub in G:a = G[sub]\n",
    "                    else:\n",
    "                      pos = 0;a = 0\n",
    "                      while sub >= 1 << pos:\n",
    "                          if sub >> pos & 1:a += quantity[pos]\n",
    "                          pos += 1\n",
    "                      G[sub] = a\n",
    "                    F[i][comb] = a <= v and F[i-1][comb-sub]\n",
    "        return F[-1][-1]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        count = collections.Counter(nums)\n",
    "        count = list(count.values())\n",
    "        m, n = len(count), len(quantity)\n",
    "\n",
    "        @functools.cache\n",
    "        def check(state: int, num_count: int) -> bool:\n",
    "            for i in range(n):\n",
    "                if state & (1 << i) == 0:\n",
    "                    continue\n",
    "                num_count -= quantity[i]\n",
    "                if num_count < 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        # dp[i][s]表示前i个数能够满足状态s下的顾客订单要求\n",
    "        dp = [[False] * (1 << n) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, m + 1):\n",
    "            curr_count = count[i - 1]\n",
    "            for state in range(1 << n):\n",
    "                if dp[i - 1][state]:\n",
    "                    dp[i][state] = True\n",
    "                    continue\n",
    "                j = state\n",
    "                while j != 0:\n",
    "                    if dp[i - 1][j] and check(state & (~j), curr_count):\n",
    "                        dp[i][state] = True\n",
    "                        break\n",
    "                    j = (j - 1) & state\n",
    "                if not dp[i][state] and check(state, curr_count):\n",
    "                    dp[i][state] = True\n",
    "\n",
    "        return dp[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        data = list(Counter(nums).values())\n",
    "        # print(data)\n",
    "        n = len(quantity)\n",
    "        al = (1 << n) - 1\n",
    "        sm = [0 for _ in range(1 << n)]\n",
    "        for i in range(1, 1 << n):\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1:\n",
    "                    # 这个位置上的和是什么\n",
    "                    sm[i] = quantity[j] + sm[i - (1 << j)]\n",
    "                    break\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, state):\n",
    "            if i < 0:\n",
    "                return False\n",
    "            if sm[state] <= data[i]:\n",
    "                return True\n",
    "            # 枚举子集\n",
    "            other = state\n",
    "            while other != 0:\n",
    "                rest = state - other\n",
    "                if data[i] >= sm[rest] and dfs(i - 1, other):\n",
    "                    return True\n",
    "                other = (other - 1) & state\n",
    "            return False\n",
    "        ans = dfs(len(data) - 1, al)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        data = list(Counter(nums).values())\n",
    "        # print(data)\n",
    "        n = len(quantity)\n",
    "        al = (1 << n) - 1\n",
    "        sm = [0 for _ in range(1 << n)]\n",
    "        for i in range(1, 1 << n):\n",
    "            tmp = 0\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1:\n",
    "                    # 这个位置上的和是什么\n",
    "                    tmp += quantity[j]\n",
    "            sm[i] = tmp\n",
    "        # print(sm)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, state):\n",
    "            if i < 0:\n",
    "                return False\n",
    "            if sm[state] <= data[i]:\n",
    "                return True\n",
    "            # 枚举子集\n",
    "            other = state\n",
    "            while other != 0:\n",
    "                rest = state - other\n",
    "                if data[i] >= sm[rest] and dfs(i - 1, other):\n",
    "                    return True\n",
    "                other = (other - 1) & state\n",
    "            return False\n",
    "        ans = dfs(len(data) - 1, al)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        data = list(Counter(nums).values())\n",
    "        # print(data)\n",
    "        n = len(quantity)\n",
    "        al = (1 << n) - 1\n",
    "        sm = [0 for _ in range(1 << n)]\n",
    "        for i in range(1, 1 << n):\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1:\n",
    "                    # 这个位置上的和是什么\n",
    "                    sm[i] = quantity[j] + sm[i - (1 << j)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, state):\n",
    "            if i < 0:\n",
    "                return False\n",
    "            if sm[state] <= data[i]:\n",
    "                return True\n",
    "            # 枚举子集\n",
    "            other = state\n",
    "            while other != 0:\n",
    "                rest = state - other\n",
    "                if data[i] >= sm[rest] and dfs(i - 1, other):\n",
    "                    return True\n",
    "                other = (other - 1) & state\n",
    "            return False\n",
    "        ans = dfs(len(data) - 1, al)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnts = collections.Counter(nums)\n",
    "        \n",
    "        vals = sorted(cnts.values(), reverse = True)\n",
    "\n",
    "        m = len(quantity)\n",
    "\n",
    "        dp = [0] * (1 << m)\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            need = 0\n",
    "            for j in range(m):\n",
    "                if (1 << j) & i:\n",
    "                    need += quantity[j]\n",
    "\n",
    "            dp[i] = need \n",
    "\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, state):\n",
    "            if state == 0:\n",
    "                return True\n",
    "\n",
    "            if cur == -1:\n",
    "                return False\n",
    "\n",
    "            sub = state\n",
    "            while sub:\n",
    "                if vals[cur] >= dp[sub]:\n",
    "                    if dfs(cur - 1, state ^ sub):\n",
    "                        return True\n",
    "\n",
    "                sub = (sub - 1) & state\n",
    "\n",
    "            return dfs(cur - 1, state)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        return dfs(len(vals) - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        cnts = collections.Counter(nums)\n",
    "        \n",
    "        vals = sorted(cnts.values(), reverse = True)\n",
    "\n",
    "        m = len(quantity)\n",
    "\n",
    "        dp = [0] * (1 << m)\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            need = 0\n",
    "            for j in range(m):\n",
    "                if (1 << j) & i:\n",
    "                    need += quantity[j]\n",
    "\n",
    "            dp[i] = need \n",
    "\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, state):\n",
    "            if state == 0:\n",
    "                return True\n",
    "\n",
    "            if cur == -1:\n",
    "                return False\n",
    "\n",
    "            sub = state\n",
    "            while sub:\n",
    "                if vals[cur] >= dp[sub]:\n",
    "                    if dfs(cur - 1, state ^ sub):\n",
    "                        return True\n",
    "\n",
    "                sub = (sub - 1) & state\n",
    "\n",
    "            return dfs(cur - 1, state)\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        return dfs(len(vals) - 1, (1 << m) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        n=len(quantity)\n",
    "        m=1<<n\n",
    "        cnt=Counter(nums)\n",
    "        cnt=list(cnt.values())\n",
    "        k=len(cnt)\n",
    "        Sump=[0]*m\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i>>j&1: Sump[i]+=quantity[j]\n",
    "        #预处理状态需求数\n",
    "        @cache\n",
    "        def dfs(c,mask):\n",
    "            if mask==0: return True\n",
    "            if c==-1: return False\n",
    "            s=mask\n",
    "            while s:\n",
    "                if Sump[s]<=cnt[c] and dfs(c-1,mask^s):\n",
    "                    return True\n",
    "                s=(s-1)&mask\n",
    "            if dfs(c-1,mask): return True\n",
    "            return False\n",
    "        return dfs(k-1,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def canDistribute(self, nums: List[int], \n",
    "                    quantity: List[int]) -> bool:    \n",
    "    cnts = list(Counter(nums).values())\n",
    "    m = len(quantity)\n",
    "    n = len(cnts)\n",
    "    sums = [0] * (1 << m)\n",
    "    for mask in range(1 << m):\n",
    "      for i in range(m):\n",
    "        if mask & (1 << i): sums[mask] += quantity[i]\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def dp(mask: int, i: int) -> bool:\n",
    "      if not mask: return True\n",
    "      if i < 0: return False\n",
    "      \n",
    "      cur = mask\n",
    "      while cur:\n",
    "        if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):\n",
    "          return True\n",
    "        cur = (cur - 1) & mask\n",
    "      \n",
    "      return dp(mask, i - 1)\n",
    "    \n",
    "    return dp((1 << m) - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        n=len(quantity)\n",
    "        m=1<<n\n",
    "        cnt=Counter(nums)\n",
    "        cnt=list(cnt.values())\n",
    "        k=len(cnt)\n",
    "        Sump=[0]*m\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i>>j&1: Sump[i]+=quantity[j]\n",
    "        #预处理状态需求数\n",
    "        @cache\n",
    "        def dfs(c,mask):\n",
    "            if mask==0: return True\n",
    "            if c==-1: return False\n",
    "            s=mask\n",
    "            while s:\n",
    "                if Sump[s]<=cnt[c] and dfs(c-1,mask^s):\n",
    "                    return True\n",
    "                s=(s-1)&mask\n",
    "            if dfs(c-1,mask): return True\n",
    "            return False\n",
    "        return dfs(k-1,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def canDistribute(self, nums: List[int], \n",
    "                    quantity: List[int]) -> bool:    \n",
    "    cnts = list(Counter(nums).values())\n",
    "    m = len(quantity)\n",
    "    n = len(cnts)\n",
    "    sums = [0] * (1 << m)\n",
    "    for mask in range(1 << m):\n",
    "      for i in range(m):\n",
    "        if mask & (1 << i): sums[mask] += quantity[i]\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def dp(mask: int, i: int) -> bool:\n",
    "      if not mask: return True\n",
    "      if i < 0: return False\n",
    "      \n",
    "      cur = mask\n",
    "      while cur:\n",
    "        if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):\n",
    "          return True\n",
    "        cur = (cur - 1) & mask\n",
    "      \n",
    "      return dp(mask, i - 1)\n",
    "    \n",
    "    return dp((1 << m) - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        count = collections.Counter(nums)\n",
    "        count = list(count.values())\n",
    "        m, n = len(count), len(quantity)\n",
    "\n",
    "        @functools.cache\n",
    "        def backtracking(index: int, rest: int, state: int):\n",
    "            \"\"\"\n",
    "            index:当前使用的整数索引\n",
    "            rest:当前使用的数剩余的个数\n",
    "            state:顾客的分配状态\n",
    "            \"\"\"\n",
    "            # 所有顾客均被成功分配，返回True\n",
    "            if state == (1 << n) - 1:\n",
    "                return True\n",
    "            # 当前已无多余整数可以分配，剪枝\n",
    "            if index == m:\n",
    "                return False\n",
    "            # 尝试为下一个顾客分配\n",
    "            for j in range(n):\n",
    "                if state & (1 << j) == 0:\n",
    "                    if rest >= quantity[j]:\n",
    "                        if backtracking(index, rest - quantity[j], state | (1 << j)):\n",
    "                            return True\n",
    "                    # 当前数不足以分配，只能使用下一个数分配    \n",
    "                    else:\n",
    "                        if index + 1 < m and backtracking(index + 1, count[index + 1], state):\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        return backtracking(0, count[0], 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        count = collections.Counter(nums)\n",
    "        count = list(count.values())\n",
    "        m, n = len(count), len(quantity)\n",
    "\n",
    "        @functools.cache\n",
    "        def backtracking(index: int, rest: int, state: int):\n",
    "            \"\"\"\n",
    "            index:当前使用的整数索引\n",
    "            rest:当前使用的数剩余的个数\n",
    "            state:顾客的分配状态\n",
    "            \"\"\"\n",
    "            # 所有顾客均被成功分配，返回True\n",
    "            if state == (1 << n) - 1:\n",
    "                return True\n",
    "            # 当前已无多余整数可以分配，剪枝\n",
    "            if index == m:\n",
    "                return False\n",
    "            # 尝试为下一个顾客分配\n",
    "            for j in range(n):\n",
    "                if state & (1 << j) == 0:\n",
    "                    if rest >= quantity[j]:\n",
    "                        if backtracking(index, rest - quantity[j], state | (1 << j)):\n",
    "                            return True\n",
    "                    # 当前数不足以分配，只能使用下一个数分配    \n",
    "                    else:\n",
    "                        if index + 1 < m and backtracking(index + 1, count[index + 1], state):\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        return backtracking(0, count[0], 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        count = collections.Counter(nums)\n",
    "        count = list(count.values())\n",
    "        m, n = len(count), len(quantity)\n",
    "        count.sort(reverse=True)\n",
    "\n",
    "        @functools.cache\n",
    "        def backtracking(index: int, rest: int, state: int):\n",
    "            \"\"\"\n",
    "            index:当前使用的整数索引\n",
    "            rest:当前使用的数剩余的个数\n",
    "            state:顾客的分配状态\n",
    "            \"\"\"\n",
    "            # 所有顾客均被成功分配，返回True\n",
    "            if state == (1 << n) - 1:\n",
    "                return True\n",
    "            # 当前已无多余整数可以分配，剪枝\n",
    "            if index == m:\n",
    "                return False\n",
    "            # 尝试为下一个顾客分配\n",
    "            for j in range(n):\n",
    "                if state & (1 << j) == 0:\n",
    "                    if rest >= quantity[j]:\n",
    "                        if backtracking(index, rest - quantity[j], state | (1 << j)):\n",
    "                            return True\n",
    "                    # 当前数不足以分配，只能使用下一个数分配    \n",
    "                    else:\n",
    "                        if index + 1 < m and backtracking(index + 1, count[index + 1], state):\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        return backtracking(0, count[0], 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        c1=Counter(nums)\n",
    "        ps=[]\n",
    "        for i,(k,v) in enumerate(c1.items()):\n",
    "            ps.append((v,i))\n",
    "        ps.sort(reverse=True)\n",
    "        n=len(ps)\n",
    "        m=len(quantity)\n",
    "        u=(1<<m)-1\n",
    "        @cache\n",
    "        def dfs(s, idx, take):\n",
    "            if not s:\n",
    "                return True\n",
    "            if idx==n:\n",
    "                return False\n",
    "            flag=False\n",
    "            takeall=ps[idx][0]\n",
    "            for j in range(m):  # 尝试分配顾客j\n",
    "                if s&(1<<j):\n",
    "                        if take+quantity[j]<=takeall:\n",
    "                            flag=dfs(s^(1<<j), idx, take+quantity[j])\n",
    "                        else:\n",
    "                            flag=dfs(s, idx+1, 0)\n",
    "                        if flag: return True\n",
    "\n",
    "            return False\n",
    "        return dfs(u,0, 0)\n",
    "        \n",
    "    def canDistribute_0(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        c1=Counter(nums)\n",
    "        ps=[]\n",
    "        for i,(k,v) in enumerate(c1.items()):\n",
    "            ps.append((v,i))\n",
    "        ps.sort(reverse=True)\n",
    "        n=len(ps)\n",
    "        m=len(quantity)\n",
    "        u=(1<<m)-1\n",
    "        @cache\n",
    "        def dfs(s, idx, rest):\n",
    "            if not s:\n",
    "                return True\n",
    "            if idx==n:\n",
    "                return False\n",
    "            flag=False\n",
    "            for j in range(m):  # 尝试分配顾客j\n",
    "                if s&(1<<j):\n",
    "                        if rest>=quantity[j]:\n",
    "                            flag=dfs(s^(1<<j), idx, rest-quantity[j])\n",
    "                        else:\n",
    "                            if idx+1<n:\n",
    "                                flag=dfs(s, idx+1, ps[idx+1][0])\n",
    "                        if flag: return True\n",
    "\n",
    "            return False\n",
    "        return dfs(u,0, ps[0][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        ## 看到这种题，len(quantity)<=10，就可以考虑状态dp\n",
    "        c1=Counter(nums)\n",
    "        ps=[]\n",
    "        for i,(k,v) in enumerate(c1.items()):\n",
    "            ps.append((v,i))\n",
    "        ps.sort(reverse=True)\n",
    "        n=len(ps)\n",
    "        m=len(quantity)\n",
    "        u=(1<<m)-1\n",
    "        @cache\n",
    "        def dfs(s, idx, take):\n",
    "            if not s:\n",
    "                return True\n",
    "            if idx==n:\n",
    "                return False\n",
    "            flag=False\n",
    "            takeall=ps[idx][0]\n",
    "            for j in range(m):  # 尝试分配顾客j\n",
    "                if s&(1<<j):\n",
    "                    if take+quantity[j]<=takeall:\n",
    "                        flag=dfs(s^(1<<j), idx, take+quantity[j])\n",
    "                    else:\n",
    "                        flag=dfs(s, idx+1, 0)\n",
    "                    if flag: return True\n",
    "\n",
    "            return False\n",
    "        return dfs(u,0, 0)\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        c1=Counter(nums)\n",
    "        ps=[]\n",
    "        for i,(k,v) in enumerate(c1.items()):\n",
    "            ps.append((v,i))\n",
    "        ps.sort(reverse=True)\n",
    "        n=len(ps)\n",
    "        m=len(quantity)\n",
    "        u=(1<<m)-1\n",
    "        @cache\n",
    "        def dfs(s, idx, take):\n",
    "            if not s:\n",
    "                return True\n",
    "            if idx==n:\n",
    "                return False\n",
    "            flag=False\n",
    "            takeall=ps[idx][0]\n",
    "            for j in range(m):  # 尝试分配顾客j\n",
    "                if s&(1<<j):\n",
    "                        if take+quantity[j]<=takeall:\n",
    "                            flag=dfs(s^(1<<j), idx, take+quantity[j])\n",
    "                        else:\n",
    "                            flag=dfs(s, idx+1, 0)\n",
    "                        if flag: return True\n",
    "\n",
    "            return False\n",
    "        return dfs(u,0, 0)\n",
    "        \n",
    "    def canDistribute_0(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        c1=Counter(nums)\n",
    "        ps=[]\n",
    "        for i,(k,v) in enumerate(c1.items()):\n",
    "            ps.append((v,i))\n",
    "        ps.sort(reverse=True)\n",
    "        n=len(ps)\n",
    "        m=len(quantity)\n",
    "        u=(1<<m)-1\n",
    "        @cache\n",
    "        def dfs(s, idx, rest):\n",
    "            if not s:\n",
    "                return True\n",
    "            if idx==n:\n",
    "                return False\n",
    "            flag=False\n",
    "            for j in range(m):  # 尝试分配顾客j\n",
    "                if s&(1<<j):\n",
    "                        if rest>=quantity[j]:\n",
    "                            flag=dfs(s^(1<<j), idx, rest-quantity[j])\n",
    "                        else:\n",
    "                            if idx+1<n:\n",
    "                                flag=dfs(s, idx+1, ps[idx+1][0])\n",
    "                        if flag: return True\n",
    "\n",
    "            return False\n",
    "        return dfs(u,0, ps[0][0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:\n",
    "        c1=Counter(nums)\n",
    "        ps=[]\n",
    "        for i,(k,v) in enumerate(c1.items()):\n",
    "            ps.append((v,i))\n",
    "        ps.sort(reverse=True)\n",
    "        n=len(ps)\n",
    "        m=len(quantity)\n",
    "        u=(1<<m)-1\n",
    "        @cache\n",
    "        def dfs(s, idx, take):\n",
    "            if not s:\n",
    "                return True\n",
    "            if idx==n:\n",
    "                return False\n",
    "            takeall=ps[idx][0]\n",
    "            for j in range(m):  # 尝试分配顾客j\n",
    "                if s&(1<<j):\n",
    "                    if take+quantity[j]<=takeall:\n",
    "                        if dfs(s^(1<<j), idx, take+quantity[j]):return True\n",
    "                    else:\n",
    "                        if dfs(s, idx+1, 0):return True\n",
    "            return False\n",
    "        return dfs(u,0, 0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
